Binary Search

Instructions

1. Hiding behind these doors lies a cute dog
2. Let min = 1st door and max = n doors
3. One of three scenarios proceed:
• The nth door selected was the correct door
• The nth door selected was lower on the list relative to the correct door. If so, then the new min becomes the nth door selected and the new range becomes [n : max]
• The nth door selected was higher on the list relative to the correct door. If so, the new max becomes the nth door selected and the new range becomes [min : n]

Analysis

If you repeatedlly select the door at the position in the middle for every try, then the number of tries entail:

• Base-2 log of n (worst case), the number of times you need to divide n by 2 in order to get 1
• One (best case), the first door you select is the correct one

n	base-2 log ofn
1	0
2	1
4	2
8	3
16	4
32	5
64	6
128	7
256	8
512	9
1,024	10
1,048,576	20
2,097,152	21

For a better explanation: Binary Search

Count: